1730B - Meeting on the Line - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;

#define fore(i, l, r) for (lli i = (l) - ((l) > (r)); i != (r) - ((l) > (r)); i += 1 - 2 * ((l) > (r)))
#define all(a) begin(a), end(a)
#define sz(a) lli(a.size())
#define pb push_back
#define f first
#define s second

#ifdef LOCAL
#include "../debug.h"
#else
#define debug(...)
#endif

using lli = long long;
using ld = long double;
using ii = pair<lli, lli>;

const lli N = 1e6 + 5;
const ld INF = 4e18 + 5;

const ld EPS = 1e-20;
#define eq(a, b) (abs((a) - (b)) <= +EPS)
#define neq(a, b) (!eq(a, b))
#define geq(a, b) ((a) - (b) >= -EPS)
#define leq(a, b) ((a) - (b) <= +EPS)
#define ge(a, b) ((a) - (b) > +EPS)
#define le(a, b) ((a) - (b) < -EPS)

lli n;
ii a[N];

template <class T>
bool umin(T& a, T b) {
  return (a = (le(a, b) ? a : b)) == b;
}

template <class T>
bool umax(T& a, T b) {
  return (a = (ge(a, b) ? a : b)) == b;
}

template <class T, class F>
pair<T, T> ternary(T lo, T hi, F f) {
  lli original_lo = lo;
  lli original_hi = hi;
  fore (it, 0, 234) {
    T m1 = lo + (hi - lo) / 3.0;
    T m2 = hi - (hi - lo) / 3.0;
    if (leq(f(m1), f(m2)))
      hi = m2;
    else
      lo = m1;
  }
  return min({make_pair(f(lo), lo), make_pair(f(hi), hi)});
}

void testCase() {
  cin >> n;
  multiset<lli> left, right;
  fore (i, 0, n) {
    cin >> a[i].f;
  }
  fore (i, 0, n) {
    cin >> a[i].s;
    right.insert(a[i].f + a[i].s);
  }
  ld ans = 0;
  ld mx = INF;
  ld prev = 0;
  ld delta = 0;
  sort(a, a + n);
  fore (i, 0, n) {
    delta += a[i].f - prev;
    prev = a[i].f;
    right.erase(right.find(a[i].f + a[i].s));
    left.insert(a[i].s - delta);
    lli mx_left = left.empty() ? 0 : *left.rbegin() + delta;
    lli mx_right = right.empty() ? 0 : *right.rbegin() - delta;
    if (umin<ld>(mx, max(mx_left, mx_right))) {
      ans = a[i].f;
    }
    if (i < n - 1 && a[i].f != a[i + 1].f) {
      debug(a[i], a[i + 1]);
      auto [best, x] = ternary<ld>(a[i].f, a[i + 1].f, [&](ld x) {
        ld cur_mx_left = mx_left + (x - a[i].f);
        ld cur_mx_right = mx_right - (x - a[i].f);
        ld mx = cur_mx_left;
        umax(mx, cur_mx_right);
        return mx;
      });
      if (umin(mx, best)) {
        debug(mx, best);
        ans = x;
      }
    }
  }
  cout << fixed << setprecision(10) << ans << '\n';
}

int main() {
  cin.tie(0)->sync_with_stdio(0), cout.tie(0);
  lli tc = 1;
  cin >> tc;
  while (tc--) {
    testCase();
  }
  return 0;
}